package sorting;


public class Sorting {


    public static void main(String[] args) {
        int[] m = {10, 1, 99, 9, 97, 6, 95, 94, 93};
        print(m);
        System.out.println("------------");
        print(quickSorting(m));
        print(bubbleSorting(m));
        print(selectSorting(m));
        print(insrtSorting(m));
    }


    /****
     * 冒泡排序
     * 时间复杂度 0（n）
     *
     */
    public static int[] bubbleSorting(int[] numArray) {
        if (isEmptyArray(numArray)) {
            return numArray;
        }
        for (int i = 0; i < numArray.length - 1; i++) {

            int count = 0;
            for (int j = 0; j < numArray.length - i - 1; j++) {
                if (numArray[j] > numArray[j + 1]) {
                    int temp = numArray[j];
                    numArray[j] = numArray[j + 1];
                    numArray[j + 1] = temp;
                }
                count++;

            }
//            System.out.println("比较次数:" + count);
//            System.out.println("第" + (i + 1) + "次排序:");
//            print(numArray);
//            System.out.println();
        }
        return numArray;
    }

    /****
     * 选择排序 O(n2)
     * 思想每一次遍历找出最小的 那个数的下标 交换至 次数-1位置
     * @param numArray
     */
    public static int[] selectSorting(int[] numArray) {
        if (isEmptyArray(numArray)) {
            return numArray;
        }
        for (int i = 0; i < numArray.length - 1; i++) {
            int index = i;
            for (int j = i; j < numArray.length; j++) {
                if (numArray[j] < numArray[index]) {
                    index = j;
                }
            }
            if (index != i) {
                int temp = numArray[i];
                numArray[i] = numArray[index];
                numArray[index] = temp;
            }
//            System.out.println();
//            System.out.println("第" + (i + 1) + "次排序:");
//            print(numArray);


        }
        return numArray;
    }

    /****
     * 插入排序
     *
     * @param numArray
     */
    public static int[] insrtSorting(int[] numArray) {
        if (isEmptyArray(numArray)) {
            return numArray;
        }
        for (int i = 1; i < numArray.length; i++) {
            int index = i;
            int subIndex = index - 1;
            int temp = numArray[i];
            boolean isChange = false;
            while (subIndex > -1 && temp < numArray[subIndex]) {
                numArray[subIndex + 1] = numArray[subIndex];
                isChange = true;
                subIndex--;
            }
            if (isChange) {
                if (subIndex == -1) {
                    subIndex = 0;
                }
                numArray[subIndex] = temp;
            }
//            System.out.println();
//            System.out.println("第" + (i + 1) + "次排序:");
//            print(numArray);

        }
        return numArray;
    }


    /****
     * 快速排序
     *  它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
     *  其中一部分的所有数据都比另外一部分的所有数据都要小
     *  ，然后再按此方法对这两部分数据分别进行快速排序，
     *  整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     * @param numArray
     * @return
     */
    public static int[] quickSorting(int[] numArray) {
        if (isEmptyArray(numArray)) {
            return numArray;
        }
        return deal(numArray, 0, numArray.length - 1);

    }

    public static int[] deal(int[] numArray, int head, int tail) {
        int current = numArray[head];
        int left = head;
        int right = tail;
        while (left != right) {

            while (numArray[right] > current && right > 0) {
                right--;
            }
            numArray[left] = numArray[right];

            while (numArray[left] < current && (left < right)) {
                left++;
            }
            numArray[right] = numArray[left];

        }
//        System.out.println();
//        System.out.println("head:"+head+ " ,tail:" + tail+"  排序:");
//        print(numArray);
        numArray[left] = current;
        if (head < tail) {
            if (left != 0) {
                deal(numArray, 0, left - 1);
            }
            if (left != tail) {
                deal(numArray, left + 1, tail);
            }

        }
        return numArray;

    }


    public static void print(int[] numArray) {
        if (numArray == null || numArray.length == 0) {
            System.out.println("[]");
            return;
        }
        System.out.print("[");
        for (int i = 0; i < numArray.length; i++) {
            System.out.print(numArray[i]);
            if (i != numArray.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
        System.out.println();

    }

    public static boolean isEmptyArray(int[] numArray) {
        return (numArray == null || numArray.length < 2) == true ? true : false;

    }
}
